#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
// 存储空间初始分配量
#define STACKINCREMENT 10
// 存储空间分配增量
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef char SElemType;
typedef struct
{
    SElemType *base; // 存储空间基址
    int top;		 // 栈顶的数组下标
    int stacksize;	 //当前栈的最大容量
} SqStack;

int InitStack(SqStack &S)
{ // 构造一个空栈 S
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S.base)
        exit(OVERFLOW);
    S.top = -1;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

int StackEmpty(SqStack S)
{
    if (S.top == -1)
        return OK;
    return ERROR;
}

int GetTop(SqStack S, SElemType &e)
{ // 若栈不空，则用 e 返回S的栈顶元素，并返回OK　　
    if (StackEmpty(S))
        return ERROR; // 空栈
    e = S.base[S.top];
    return OK;
}

int Push(SqStack &S, SElemType &e)
{ // 插入元素 e 为新的栈顶元素
    if (S.top + 1 >= S.stacksize)
    { //栈满，追加存储空间
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        if (!S.base)
            exit(OVERFLOW);
        S.stacksize += STACKINCREMENT;
    }
    S.base[++S.top] = e;
    return OK;
}

int Pop(SqStack &S, SElemType &e)
{ // 栈不空，删除S的栈顶元素，用e返回其值，并返回 OK；否则返回 ERROR
    if (StackEmpty(S))
        return ERROR; //空栈
    e = S.base[S.top--];
    return OK;
}

int match(SqStack &s, char *str)
{
    int i = 0, flag = 0;
    SElemType e;
    InitStack(s);
    while (str[i] != '\0')
    {
        switch (str[i])
        {
        case '(':
            Push(s, str[i]);
            break;
        case '[':
            Push(s, str[i]);
            break;
        case ')':
        {
            Pop(s, e);
            if (e != '(')
                flag = 1;
        }
        break;
        case ']':
        {
            Pop(s, e);
            if (e != '[')
                flag = 1;
        }
        break;
        default:
            break;
        }
        if (flag)
            break;
        i++;
    }
    if (!flag && StackEmpty(s))
        printf("括号匹配成功!");
    else
        printf("括号匹配失败!");
    return OK;
}

int main()
{
    char str[100], enter;
    SqStack s;
    InitStack(s);
    printf("请输入字符串:");
    scanf("%s", str);
    //	scanf("%c",&enter);
    match(s, str);
    return 0;
}
